package com.example.demo.zaqizabatest.leetcode.day7;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 */
public class Solution3 {

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        TreeNode rootSame = root;
        return compareNodes(root, rootSame);
    }

    private boolean compareNodes(TreeNode node, TreeNode compareNode) {
        if ((node.left != null && compareNode.right == null)
                || (node.left == null && compareNode.right != null)) {
            return false;
        }
        if ((node.right != null && compareNode.left == null)
                || (node.right == null && compareNode.left != null)) {
            return false;
        }
        if (node.left != null && compareNode.right != null){
            if (node.left.val == compareNode.right.val){
                 if (!compareNodes(node.left, compareNode.right)) {
                     return false;
                 }
            } else {
                return false;
            }
        }
        if (node.right != null && compareNode.left != null){
            if (node.right.val == compareNode.left.val){
                if (!compareNodes(node.right, compareNode.left)) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
// [7,-64,-64,-6,-90,-90,-6,88,-44,68,-65,-76,68,-44,88]
    public static void main(String[] args) {
        Solution3 solution1 = new Solution3();
        TreeNode root1 = new TreeNode(7);
        TreeNode root2 = new TreeNode(-64);
        TreeNode root3 = new TreeNode(-64);
        TreeNode root4 = new TreeNode(-6);
        TreeNode root5 = new TreeNode(-90);
        TreeNode root6 = new TreeNode(-90);
        TreeNode root7 = new TreeNode(-6);

        TreeNode root8 = new TreeNode(88);
        TreeNode root9 = new TreeNode(-44);
        TreeNode root10 = new TreeNode(-68);
        TreeNode root11 = new TreeNode(-65);
        TreeNode root12 = new TreeNode(-76);
        TreeNode root13 = new TreeNode(-68);
        TreeNode root14 = new TreeNode(-44);
        TreeNode root15 = new TreeNode(88);
        root1.left = root2;
        root1.right = root3;

        root2.left = root4;
        root2.right = root5;

        root3.left = root6;
        root3.right = root7;

        root4.left = root8;
        root4.right =root9;

        root5.left = root10;
        root5.right = root11;

        root6.left = root12;
        root6.right = root13;

        root7.left = root14;
        root7.right = root15;


        System.out.println(solution1.isSymmetric(root1));

    }
}
